package com.example.tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Leetcode648_ReplaceWords {
    public static void main(String[] args) {

        List<String> roots = new ArrayList<>();
//        roots.add("cat");
//        roots.add(("bat"));
//        roots.add("rat");
//        String sentence = "the cattle was rattled by the battery";

        // "a", "aa", "aaa", "aaaa"
//        roots.add("a");
//        roots.add("aa");
//        roots.add("aaa");
//        String sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa";

        // "ac","ab"
        roots.add("ac");
        roots.add("ab");
        String sentence = "it is abnormal that this solution is accepted";

        System.out.println(replaceWords(roots, sentence));

    }

    public static String replaceWords(List<String> roots, String sentence) {
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            for (String root : roots) {
                if (words[i].length() >= root.length()
                        && words[i].substring(0, root.length()).equals(root))
                    words[i] = root;
            }
            sb.append(words[i]).append(" ");
        }

        return sb.substring(0, sb.length() - 1);
    }

    public String replaceWords2(List<String> roots, String sentence) {
        Set<String> rootset = new HashSet();
        for (String root: roots) rootset.add(root);

        StringBuilder ans = new StringBuilder();
        for (String word: sentence.split("\\s+")) {
            String prefix = "";
            for (int i = 1; i <= word.length(); ++i) {
                prefix = word.substring(0, i);
                if (rootset.contains(prefix)) break;
            }
            if (ans.length() > 0) ans.append(" ");
            ans.append(prefix);
        }
        return ans.toString();
    }
}
